// 2025/4/1
// https://leetcode.cn/problems/longest-valid-parentheses/description/?envType=study-plan-v2&envId=top-100-liked
// 最长有效括号

class Solution {
    public:
        int longestValidParentheses(string s) {
            int n = s.size(), ans = 0;
            vector<int> dp(n, 0);
            for(int i = 1; i < n; i++)
            {
                if(s[i] == ')')
                {
                    if(s[i - 1] == '(') 
                        dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
                    else if(i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(')
                        dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
                    ans = max(ans, dp[i]);
                }
            }
            return ans;
        }
    };

class Solution {
    public:
        int longestValidParentheses(string s) {
            int n = s.size(), ans = 0;
            stack<int> st; st.push(-1);
            for(int i = 0; i < n; i++)
            {
                if(s[i] == '(') st.push(i);
                else if(st.size() > 1)
                {
                    st.pop();
                    ans = max(ans, i - st.top());
                }
                else st.top() = i;
            }
            return ans;
        }
    };

// 只有单种括号时很值得借鉴
class Solution {
    public:
        int longestValidParentheses(string s) {
            int left = 0, right = 0, maxlength = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s[i] == '(') {
                    left++;
                } else {
                    right++;
                }
                if (left == right) {
                    maxlength = max(maxlength, 2 * right);
                } else if (right > left) {
                    left = right = 0;
                }
            }
            left = right = 0;
            for (int i = (int)s.length() - 1; i >= 0; i--) {
                if (s[i] == '(') {
                    left++;
                } else {
                    right++;
                }
                if (left == right) {
                    maxlength = max(maxlength, 2 * left);
                } else if (left > right) {
                    left = right = 0;
                }
            }
            return maxlength;
        }
    };